﻿/**
 * @file std_hash.c
 * Copyright (c) 2019 Gaaagaa. All rights reserved.
 * 
 * @author  : Gaaagaa
 * @date    : 2019-09-09
 * @version : 1.0.0.0
 * @brief   : 使用 C API 的接口形式实现 散列 容器。
 */

/**
 * The MIT License (MIT)
 * Copyright (c) Gaaagaa. All rights reserved.
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy of
 * this software and associated documentation files (the "Software"), to deal in
 * the Software without restriction, including without limitation the rights to
 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
 * of the Software, and to permit persons to whom the Software is furnished to do
 * so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
 * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
 * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
 * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#include "std_hash.h"
#include "std_debug.h"
#include "std_hash.inl"

#include <math.h>

////////////////////////////////////////////////////////////////////////////////

#ifdef __GNUC__
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-function"
#endif // __GNUC__

////////////////////////////////////////////////////////////////////////////////

//====================================================================

// 
// xstd_hash_t 的内部相关操作接口
// 

/**********************************************************/
/**
 * @brief 计算节点存储的元素对象 散列键值 的通用函数。
 * 
 * @param [in ] xet_vptr : 节点存储的元素对象。
 * @param [in ] xet_ctxt : 节点元素的上下文信息。
 * 
 * @return xhash_nkey_t : 返回 散列键值。
 */
static xhash_nkey_t hash_nkey_elem(
                        xstd_elem_t xet_vptr,
                        xstd_ctxt_t xet_ctxt)
{
    return std_hash_nkey_calc((xhash_mptr_t)xet_vptr, xet_ctxt->xstd_esize);
}

/**********************************************************/
/**
 * @brief 清空 xstd_hash_t 对象的散列桶。
 * 
 * @param [in,out] xhash_this : xstd_hash_t 对象。
 * @param [in    ] xst_bsize  : 
 * 清空后散列桶的容量。必须为 2^N 的整数值，且 >= XHASH_BUCKET_MINSIZE。
 */
static inline xhash_void_t hash_bucket_clear(
                                xhash_this_t xhash_this,
                                xhash_size_t xst_bsize)
{
    XASSERT(xst_bsize >= XHASH_BUCKET_MINSIZE);
    XASSERT(0 == (xst_bsize & (xst_bsize - 1)));

    const xhash_lter_t xlter_hend = XHASH_LTER_END(xhash_this);

    xhash_vter_t xvter_trav = XHASH_NULL;
    xhash_vter_t xvter_bend = XHASH_NULL;

    if (xst_bsize != XHASH_BUCKET_SIZE(xhash_this))
    {
        if (XHASH_NULL != XHASH_BUCKET_VPTR(xhash_this))
        {
            XHASH_DEALLOC(xhash_this, XHASH_BUCKET_VPTR(xhash_this));
        }

        XHASH_BUCKET_VPTR(xhash_this) = 
                (xhash_vter_t)XHASH_MALLOC(
                    xhash_this, xst_bsize * sizeof(xhash_vkey_t));
        XASSERT(XHASH_NULL != XHASH_BUCKET_VPTR(xhash_this));
    
        XHASH_BUCKET_SIZE(xhash_this) = xst_bsize;
        XHASH_BUCKET_MASK(xhash_this) = xst_bsize - 1;
    }

    xvter_trav = XHASH_BUCKET_VPTR(xhash_this);
    xvter_bend = XHASH_BUCKET_VPTR(xhash_this) + xst_bsize;
    for (; xvter_trav != xvter_bend; xvter_trav += 1)
    {
        xvter_trav->xlter_head = xlter_hend;
        xvter_trav->xlter_tail = xlter_hend;
    }
}

/**********************************************************/
/**
 * @brief 若散列表所存储 节点数量 变更时，判断散列桶是否会超负载。
 * 
 * @param [in ] xhash_this : xstd_hash_t 对象。
 * @param [in ] xst_resize : 散列表期望存储的 节点数量。
 * 
 * @return xhash_bool_t : 散列桶是否会超负载。
 */
static inline xhash_bool_t hash_bucket_is_overload(
                                xhash_this_t xhash_this,
                                xhash_size_t xst_resize)
{
    return (XHASH_BUCKET_MAXF(xhash_this) < 
                (((xhash_float_t)(xst_resize) / 
                 ((xhash_float_t)XHASH_BUCKET_SIZE(xhash_this)))));
}

/**********************************************************/
/**
 * @brief 
 * 当期望 散列表 能存储的 节点数量 达到所指定的 值 时，
 * 计算出符合最少要求的 散列桶数量。
 * 
 * @param [in ] xhash_this : xstd_hash_t 对象。
 * @param [in ] xst_resize : 期望散列表能存储的节点数量达到所指定的值。
 * 
 * @return xhash_size_t : 符合最少要求的 散列桶数量。
 */
static inline xhash_size_t hash_bucket_req_minsize(
                                xhash_this_t xhash_this,
                                xhash_size_t xst_resize)
{
    return (xhash_size_t)(
        ceil((xhash_float_t)(xst_resize) / XHASH_BUCKET_MAXF(xhash_this)));
}

/**********************************************************/
/**
 * @brief 
 * 当期望 散列表 能存储的 节点数量 达到所指定的 值 时，
 * 计算出符合要求的 散列桶数量。
 * 
 * @param [in ] xhash_this : xstd_hash_t 对象。
 * @param [in ] xst_resize : 期望散列表能存储的节点数量达到所指定的值。
 * 
 * @return xhash_size_t : 符合要求的 散列桶数量。
 */
static xhash_size_t hash_bucket_calc_bsize(
                        xhash_this_t xhash_this,
                        xhash_size_t xst_resize)
{
    xhash_size_t xst_bsize = hash_bucket_req_minsize(xhash_this, xst_resize);

    if (xst_bsize < XHASH_BUCKET_MINSIZE)
    {
        xst_bsize = XHASH_BUCKET_MINSIZE;
    }

    if (XHASH_BUCKET_SIZE(xhash_this) >= xst_bsize)
    {
        return XHASH_BUCKET_SIZE(xhash_this);
    }

    if ((XHASH_BUCKET_SIZE(xhash_this) < 512) &&
        ((XHASH_BUCKET_SIZE(xhash_this) * 8) >= xst_bsize))
    {
        return (XHASH_BUCKET_SIZE(xhash_this) * 8);
    }

    return xst_bsize;
}

/**********************************************************/
/**
 * @brief 重新调整 散列桶容器 的布局，以便适应新指定的 散列桶 数量。
 * 
 * @param [in,out] xhash_this : xstd_hash_t 对象。
 * @param [in    ] xst_bsize  : 新指定的 散列桶 数量。
 */
static xhash_void_t hash_bucket_rehash(
                        xhash_this_t xhash_this,
                        xhash_size_t xst_bsize)
{
    XASSERT(xst_bsize <= std_floor2pow(XHASH_BUCKET_MAX_SIZE(xhash_this)));

    //======================================

    const xhash_lter_t xlter_hend = XHASH_LTER_END(xhash_this);

    xhash_vter_t xhash_vkey = XHASH_NULL;
    xhash_elem_t xhash_elem = XHASH_NULL;
    xhash_lter_t xlter_trav = XHASH_NULL;
    xhash_lter_t xlter_next = XHASH_NULL;
    xhash_lter_t xlter_tail = XHASH_NULL;
    xhash_lter_t xlter_swap = XHASH_NULL;

    //======================================

    xst_bsize = std_ceil2pow(xst_bsize);
    hash_bucket_clear(xhash_this, xst_bsize);

    //======================================

    xlter_trav = XHASH_LTER_BEGIN(xhash_this);
    for (xlter_next  = xlter_trav;
         xlter_trav != xlter_hend;
         xlter_trav  = xlter_next)
    {
        //======================================

        xhash_elem = XHASH_LTER_ELEM(xlter_trav);
        xlter_next = XHASH_LTER_NEXT(xlter_next);

        xhash_vkey = XHASH_BUCKET_VTER(xhash_this, xhash_elem);

        //======================================

        if (xhash_vkey->xlter_head == xlter_hend)
        {
            xhash_vkey->xlter_head = xlter_trav;
            xhash_vkey->xlter_tail = xlter_trav;
            continue;
        }

        xlter_tail = xhash_vkey->xlter_tail;
        if (XHASH_ELEM_EQ(xhash_this, xhash_elem, XHASH_LTER_ELEM(xlter_tail)))
        {
            xlter_tail = XHASH_LTER_NEXT(xlter_tail);
            if (xlter_tail != xlter_trav)
            {
                XHASH_LTER_SPLICE(xlter_tail, xlter_trav, xlter_next, xlter_swap);
            }

            xhash_vkey->xlter_tail = xlter_trav;
            continue;
        }

        //======================================

        for (;;)
        {
            if (xhash_vkey->xlter_head == xlter_tail)
            {
                XHASH_LTER_SPLICE(xlter_tail, xlter_trav, xlter_next, xlter_swap);
                xhash_vkey->xlter_head = xlter_trav;
                break;
            }

            xlter_tail = XHASH_LTER_PREV(xlter_tail);
            if (XHASH_ELEM_EQ(xhash_this, xhash_elem, XHASH_LTER_ELEM(xlter_tail)))
            {
                xlter_tail = XHASH_LTER_NEXT(xlter_tail);
                XHASH_LTER_SPLICE(xlter_tail, xlter_trav, xlter_next, xlter_swap);
                break;
            }
        }

        //======================================
    }

    //======================================
}

/**********************************************************/
/**
 * @brief 查找指定 节点元素 是否已位于 xstd_hash_t 对象中。
 * 
 * @param [in ] xhash_this : xstd_hash_t 对象。
 * @param [in ] xhash_elem : 所查找的 节点元素 对象。
 * @param [in ] xhash_nkey : 节点元素 对象的 散列键值。
 * @param [out] xhash_find : 查找操作的结果。
 * 
 * @return xhash_lter_t : 返回相应的迭代器位置。
 * - 若 xhash_find == XHASH_TRUE，则表示 xhash_elem 已存在于容器中，
 *   此时返回的 xhash_lter_t 对应其迭代器位置。
 * - 若 xhash_find == XHASH_FALSE，则表示 xhash_elem 未存在于容器中，
 *   此时返回的 xhash_lter_t，则可作为 前置插入 xhash_elem 的迭代器位置。
 */
static xhash_lter_t hash_bucket_find(
                        xhash_this_t xhash_this,
                        xhash_elem_t xhash_elem,
                        xhash_nkey_t xhash_nkey,
                        xhash_bool_t * xhash_find)
{
    xhash_vter_t xhash_vkey = XHASH_BUCKET_VKEY(xhash_this, xhash_nkey);
    xhash_lter_t xlter_trav = xhash_vkey->xlter_tail;

    if (xlter_trav == XHASH_LTER_END(xhash_this))
    {
        *xhash_find = XHASH_FALSE;
        return xlter_trav;
    }

    for (;;)
    {
        if (XHASH_ELEM_EQ(xhash_this, xhash_elem, XHASH_LTER_ELEM(xlter_trav)))
        {
            *xhash_find = XHASH_TRUE;
            return xlter_trav;
        }

        if (xlter_trav == xhash_vkey->xlter_head)
            break;
        xlter_trav = XHASH_LTER_PREV(xlter_trav);
    }

    *xhash_find = XHASH_FALSE;
    return xlter_trav;
}

/**********************************************************/
/**
 * @brief 向 散列桶 插入指定 散列键 的 新增节点迭代器。
 * 
 * @param [in,out] xhash_this : xstd_hash_t 对象。
 * @param [in    ] xhash_lter : 新增的 节点迭代器。
 * @param [in    ] xhash_nkey : xhash_lter 对应的 散列键值。
 */
static xhash_void_t hash_bucket_insert(
                        xhash_this_t xhash_this,
                        xhash_lter_t xhash_lter,
                        xhash_nkey_t xhash_nkey)
{
    xhash_vter_t xhash_vkey = XHASH_BUCKET_VKEY(xhash_this, xhash_nkey);

    if (xhash_vkey->xlter_head == XHASH_LTER_END(xhash_this))
    {
        xhash_vkey->xlter_head = xhash_lter;
        xhash_vkey->xlter_tail = xhash_lter;
    }
    else if (xhash_vkey->xlter_head == XHASH_LTER_NEXT(xhash_lter))
    {
        xhash_vkey->xlter_head = xhash_lter;
    }
    else if (xhash_vkey->xlter_tail == XHASH_LTER_PREV(xhash_lter))
    {
        xhash_vkey->xlter_tail = xhash_lter;
    }
}

/**********************************************************/
/**
 * @brief 移除 散列桶 中指定 散列键 的 节点迭代器。
 * 
 * @param [in,out] xhash_this : xstd_hash_t 对象。
 * @param [in    ] xhash_lter : 指定的 节点迭代器。
 * @param [in    ] xhash_nkey : xhash_lter 对应的 散列键值。
 */
static xhash_void_t hash_bucket_erase(
                        xhash_this_t xhash_this,
                        xhash_lter_t xhash_lter,
                        xhash_nkey_t xhash_nkey)
{
    xhash_vter_t xhash_vkey = XHASH_BUCKET_VKEY(xhash_this, xhash_nkey);

    if (xhash_vkey->xlter_tail == xhash_lter)
    {
        if (xhash_vkey->xlter_head == xhash_lter)
            xhash_vkey->xlter_head = 
            xhash_vkey->xlter_tail = XHASH_LTER_END(xhash_this);
        else
            xhash_vkey->xlter_tail = XHASH_LTER_PREV(xhash_lter);
    }
    else if (xhash_vkey->xlter_head == xhash_lter)
    {
        xhash_vkey->xlter_head = XHASH_LTER_NEXT(xhash_lter);
    }
}

/**********************************************************/
/**
 * @brief 
 * 从 散列表 中删除指定区间 [ xlter_first, xlter_last ) 的节点元素。
 * 
 * @param [in ] xhash_this  : xstd_hash_t 对象。
 * @param [in ] xlter_first : 所删除区间的 起始节点。
 * @param [in ] xlter_last  : 所删除区间的 终止节点。
 * 
 * @return xhash_lter_t : 返回 xlter_last 迭代器。
 */
static xhash_lter_t hash_table_erase(
                        xhash_this_t xhash_this,
                        xhash_lter_t xlter_first,
                        xhash_lter_t xlter_last)
{
    XASSERT(XHASH_LTER_END(xhash_this) != xlter_first);
    XASSERT(xlter_first != xlter_last);

    const xhash_lter_t xlter_hend = XHASH_LTER_END(xhash_this);

    xhash_vter_t xhash_vkey = XHASH_NULL;
    xhash_lter_t xlter_trav = xlter_first;
    xhash_lter_t xlter_tail = XHASH_NULL;
    xhash_bool_t xbt_rehead = XHASH_FALSE;

    //======================================

    xhash_vkey = XHASH_BUCKET_VTER(xhash_this, XHASH_LTER_ELEM(xlter_trav));
    xbt_rehead = (xhash_vkey->xlter_head == xlter_trav);
    xlter_tail = xhash_vkey->xlter_tail;

    for (;;)
    {
        if (xlter_trav == xlter_tail)
        {
            xlter_trav = XHASH_LTER_NEXT(xlter_trav);
            break;
        }

        xlter_trav = XHASH_LTER_NEXT(xlter_trav);

        if (xlter_trav == xlter_last)
        {
            if (xbt_rehead)
            {
                xhash_vkey->xlter_head = xlter_trav;
            }

            return XHASH_TABLE_CALL(
                erase_range, xhash_this, xlter_first, xlter_last);
        }
    }

    if (xbt_rehead)
    {
        xhash_vkey->xlter_head = xlter_hend;
        xhash_vkey->xlter_tail = xlter_hend;
    }
    else
    {
        xhash_vkey->xlter_tail = XHASH_LTER_PREV(xlter_first);
    }

    //======================================

    while (xlter_trav != xlter_last)
    {
        xhash_vkey = XHASH_BUCKET_VTER(xhash_this, XHASH_LTER_ELEM(xlter_trav));
        xlter_tail = xhash_vkey->xlter_tail;

        for (;;)
        {
            if (xlter_trav == xlter_tail)
            {
                xlter_trav = XHASH_LTER_NEXT(xlter_trav);
                break;
            }

            xlter_trav = XHASH_LTER_NEXT(xlter_trav);

            if (xlter_trav == xlter_last)
            {
                xhash_vkey->xlter_head = xlter_trav;
                return XHASH_TABLE_CALL(
                    erase_range, xhash_this, xlter_first, xlter_last);
            }
        }

        xhash_vkey->xlter_head = xlter_hend;
        xhash_vkey->xlter_tail = xlter_hend;
    }

    //======================================

    return XHASH_TABLE_CALL(erase_range, xhash_this, xlter_first, xlter_last);
}

//====================================================================

// 
// xstd_hash_t 的外部相关操作接口
// 

/**********************************************************/
/**
 * @brief 返回内部的 sizeof(xstd_hash_t) 值。
 */
xhash_size_t std_hash_sizeof(void)
{
    return (xhash_size_t)sizeof(xstd_hash_t);
}

/**********************************************************/
/**
 * @brief 计算 指定缓存块数据 的 散列键值。
 * 
 * @param [in ] xhash_mptr : 指定的缓存块数据。
 * @param [in ] xst_msize  : 指定的缓存块大小。
 * 
 * @return xhash_nkey_t : 返回 散列键值。
 */
xhash_nkey_t std_hash_nkey_calc(xhash_mptr_t xhash_mptr, xhash_size_t xst_msize)
{
#if __XSTD_TYPES_64__
    const xhash_nkey_t xkey_basis = 14695981039346656037ULL;
    const xhash_nkey_t xkey_prime = 1099511628211ULL;
#else // !__XSTD_TYPES_64__
    const xhash_nkey_t xkey_basis = 2166136261U;
    const xhash_nkey_t xkey_prime = 16777619U;
#endif // __XSTD_TYPES_64__

    xhash_nkey_t xhash_nkey = xkey_basis;
    xstd_bptr_t  xhash_vptr = (xstd_bptr_t)xhash_mptr;
    xstd_bptr_t  xhash_vend = xhash_vptr + xst_msize;

    for (; xhash_vptr != xhash_vend; ++xhash_vptr)
    {
        xhash_nkey ^= (xhash_nkey_t)*xhash_vptr;
        xhash_nkey *= xkey_prime;
    }

    return xhash_nkey;
}

/**********************************************************/
/**
 * @brief 创建 xstd_hash_t 对象。
 * @note 
 * 1. 应使用 @see std_hash_destroy() 销毁所创建的对象。
 * 2. 若 xhash_nkfunc/xhash_eqfunc 为 XHASH_NULL，则取内部默认值。
 * 
 * @param [in ] xhash_ctxt   : 散列 所存储的节点元素上下文描述信息。
 * @param [in ] xhash_nkfunc : 生成 散列键值 的回调函数。
 * @param [in ] xhash_eqfunc : 判断 节点元素是否相等 的回调函数。
 * 
 * @return xhash_this_t : 返回所创建的 xstd_hash_t 对象指针。
 */
xhash_this_t std_hash_create(
                    xhash_ctxt_t xhash_ctxt,
                    xhash_nkfunc_t xhash_nkfunc,
                    xhash_eqfunc_t xhash_eqfunc)
{
    XASSERT(0 != xhash_ctxt);
    XASSERT(0 != xhash_ctxt->xstd_etype);
    XASSERT(0 != xhash_ctxt->xstd_esize);

    xstd_altor_t   xstd_altor = XSTD_ALTOR_NCREF(xhash_ctxt->xstd_altor);
    xhash_this_t xhash_this =
        (xhash_this_t)xstd_altor->xfunc_allocate(sizeof(xstd_hash_t));
    XASSERT(XHASH_NULL != xhash_this);

    return std_hash_emplace_create(
                        xhash_this,
                        xhash_ctxt,
                        xhash_nkfunc,
                        xhash_eqfunc);
}

/**********************************************************/
/**
 * @brief 
 * 销毁 xstd_hash_t 对象，
 * 其由 @see std_hash_create() 接口所创建。
 */
xhash_void_t std_hash_destroy(xhash_this_t xhash_this)
{
    XASSERT(XHASH_NULL != xhash_this);

    xstd_altor_t xstd_altor = XHASH_ALTOR(xhash_this);

    std_hash_emplace_destroy(xhash_this);
    xstd_altor->xfunc_dealloc(xhash_this);
}

/**********************************************************/
/**
 * @brief 在指定的缓存上创建 xstd_hash_t 对象。
 * @note 
 * 1. 应使用 @see std_hash_destroy() 销毁所创建的对象。
 * 2. 若 xhash_nkfunc/xhash_eqfunc 为 XHASH_NULL，则取内部默认值。
 * 
 * @param [in ] xhash_ctxt   : 散列 所存储的节点元素上下文描述信息。
 * @param [in ] xhash_nkfunc : 生成 散列键值 的回调函数。
 * @param [in ] xhash_eqfunc : 判断 节点元素是否相等 的回调函数。
 * 
 * @return xhash_this_t : 返回所创建的 xstd_hash_t 对象指针。
 */
xhash_this_t std_hash_emplace_create(
                    xhash_this_t xhash_this,
                    xhash_ctxt_t xhash_ctxt,
                    xhash_nkfunc_t xhash_nkfunc,
                    xhash_eqfunc_t xhash_eqfunc)
{
    XASSERT(XHASH_NULL != xhash_this);
    XASSERT(XHASH_NULL != xhash_ctxt);
    XASSERT(0 != xhash_ctxt->xstd_etype);
    XASSERT(0 != xhash_ctxt->xstd_esize);

    //======================================

    XHASH_TABLE_FUNC(emplace_create, &xhash_this->xhash_table, xhash_ctxt);

    XHASH_BUCKET_RESET(xhash_this);
    hash_bucket_clear(xhash_this, XHASH_BUCKET_MINSIZE);

    //======================================

    xhash_this->xhash_nkfunc =
        (XHASH_NULL != xhash_nkfunc) ? xhash_nkfunc : hash_nkey_elem;

    xhash_this->xhash_eqfunc =
        (XHASH_NULL != xhash_eqfunc) ? xhash_eqfunc : xstd_fcmp_comm.xfunc_eq;

    //======================================

    return xhash_this;
}

/**********************************************************/
/**
 * @brief 
 * 销毁 xstd_hash_t 对象，
 * 其由 @see std_hash_emplace_create() 接口所创建。
 */
xhash_void_t std_hash_emplace_destroy(xhash_this_t xhash_this)
{
    XASSERT(XHASH_NULL != xhash_this);

    XHASH_TABLE_CALL(emplace_destroy, xhash_this);

    if (XHASH_NULL != XHASH_BUCKET_VPTR(xhash_this))
        XHASH_DEALLOC(xhash_this, XHASH_BUCKET_VPTR(xhash_this));
    XHASH_BUCKET_RESET(xhash_this);

    xhash_this->xhash_nkfunc  = XHASH_NULL;
    xhash_this->xhash_eqfunc = XHASH_NULL;
}

/**********************************************************/
/**
 * @brief 返回 xstd_hash_t 对象的 上下文信息。
 */
xhash_ctxt_t std_hash_ctxt(xhash_this_t xhash_this)
{
    XASSERT(XHASH_NULL != xhash_this);
    return XHASH_ECTXT(xhash_this);
}

/**********************************************************/
/**
 * @brief 返回 xstd_hash_t 对象的 类型标识。
 */
xhash_size_t std_hash_etype(xhash_this_t xhash_this)
{
    XASSERT(XHASH_NULL != xhash_this);
    return XHASH_ETYPE(xhash_this);
}

/**********************************************************/
/**
 * @brief 返回 xstd_hash_t 对象当前的节点数量。
 */
xhash_size_t std_hash_size(xhash_this_t xhash_this)
{
    XASSERT(XHASH_NULL != xhash_this);
    return XHASH_TABLE_SIZE(xhash_this);
}

/**********************************************************/
/**
 * @brief 判断 xstd_hash_t 对象是否为空。
 */
xhash_bool_t std_hash_empty(xhash_this_t xhash_this)
{
    XASSERT(XHASH_NULL != xhash_this);
    return (0 == XHASH_TABLE_SIZE(xhash_this));
}

/**********************************************************/
/**
 * @brief 返回 xstd_hash_t 对象可容纳最大的节点数量。
 */
xhash_size_t std_hash_maxsize(xhash_this_t xhash_this)
{
    XASSERT(XHASH_NULL != xhash_this);
    return XHASH_MAX_SIZE(xhash_this);
}

/**********************************************************/
/**
 * @brief 清除 xstd_hash_t 对象中的所有节点。
 */
xhash_void_t std_hash_clear(xhash_this_t xhash_this)
{
    XASSERT(XHASH_NULL != xhash_this);
    XHASH_TABLE_CALL(clear, xhash_this);
    hash_bucket_clear(xhash_this, XHASH_BUCKET_SIZE(xhash_this));
}

/**********************************************************/
/**
 * @brief 向 xstd_hash_t 对象插入（存入）新的 节点元素。
 * 
 * @param [in,out] xhash_this : xstd_hash_t 对象。
 * @param [in    ] xhash_elem : 插入（存入）新的 节点元素对象。
 * 
 * @param [out   ] xbt_clash  : 
 * 检测所插入的 新节点键值 是否与 xstd_hash_t 对象中
 * 原有的 节点键值 是否冲突。
 * 入参不为 XHASH_NULL 时，
 *  若返回值为 XHASH_TRUE，表示产生冲突，插入操作算是失败的；
 *  否则，返回 XHASH_FALSE，表示产生冲突，插入操作
 *  算是（新增节点）成功的。
 * 入参为 XHASH_NULL 时，则忽略该检测操作。
 * 
 * @return xhash_iter_t : 返回 xhash_elem 散列键值的对应节点。
 */
xhash_iter_t std_hash_insert(
                xhash_this_t xhash_this,
                xhash_elem_t xhash_elem,
                xhash_bool_t * xbt_clash)
{
    XASSERT(XHASH_NULL != xhash_this);
    XASSERT(XHASH_NULL != xhash_elem);

    xhash_bool_t xhash_find = XHASH_FALSE;
    xhash_nkey_t xhash_nkey = XHASH_BUCKET_NKEY(xhash_this, xhash_elem);
    xhash_lter_t xhash_lter = hash_bucket_find(xhash_this, xhash_elem, xhash_nkey, &xhash_find);
    xhash_size_t xst_resize = 0;

    if (xhash_find)
    {
        if (XHASH_NULL != xbt_clash)
            *xbt_clash = XHASH_TRUE;
        return (xhash_iter_t)xhash_lter;
    }

    xst_resize = XHASH_TABLE_SIZE(xhash_this) + 1;
    XASSERT(xst_resize <= XHASH_MAX_SIZE(xhash_this));
    if (hash_bucket_is_overload(xhash_this, xst_resize))
    {
        hash_bucket_rehash(xhash_this, hash_bucket_calc_bsize(xhash_this, xst_resize));
        xhash_lter = hash_bucket_find(xhash_this, xhash_elem, xhash_nkey, &xhash_find);
    }

    xhash_lter = XHASH_TABLE_CALL(insert, xhash_this, xhash_lter, xhash_elem);
    hash_bucket_insert(xhash_this, xhash_lter, xhash_nkey);

    if (XHASH_NULL != xbt_clash)
        *xbt_clash = XHASH_FALSE;
    return (xhash_iter_t)xhash_lter;
}

/**********************************************************/
/**
 * @brief 向 xstd_hash_t 对象安放（存入）新的 节点元素。
 * 
 * @param [in,out] xhash_this : xstd_hash_t 对象。
 * 
 * @param [in    ] xhash_elem : 
 * 安放（存入）新的 节点元素对象（使用 右值move 操作进行存储）。
 * 
 * @param [out   ] xbt_clash  : 
 * 检测所插入的 新节点键值 是否与 xstd_hash_t 对象中
 * 原有的 节点键值 是否冲突。
 * 入参不为 XHASH_NULL 时，
 *  若返回值为 XHASH_TRUE，表示产生冲突，安放操作算是失败的；
 *  否则，返回 XHASH_FALSE，表示产生冲突，安放操作
 *  算是（新增节点）成功的。
 * 入参为 XHASH_NULL 时，则忽略该检测操作。
 * 
 * @return xhash_iter_t : 返回 xhash_elem 散列键值的对应节点。
 */
xhash_iter_t std_hash_emplace(
                xhash_this_t xhash_this,
                xhash_elem_t xhash_elem,
                xhash_bool_t * xbt_clash)
{
    XASSERT(XHASH_NULL != xhash_this);
    XASSERT(XHASH_NULL != xhash_elem);

    xhash_bool_t xhash_find = XHASH_FALSE;
    xhash_nkey_t xhash_nkey = XHASH_BUCKET_NKEY(xhash_this, xhash_elem);
    xhash_lter_t xhash_lter = hash_bucket_find(xhash_this, xhash_elem, xhash_nkey, &xhash_find);

    xhash_size_t xst_resize = 0;

    if (xhash_find)
    {
        if (XHASH_NULL != xbt_clash)
            *xbt_clash = XHASH_TRUE;
        return (xhash_iter_t)xhash_lter;
    }

    xst_resize = XHASH_TABLE_SIZE(xhash_this) + 1;
    XASSERT(xst_resize <= XHASH_MAX_SIZE(xhash_this));
    if (hash_bucket_is_overload(xhash_this, xst_resize))
    {
        hash_bucket_rehash(xhash_this, hash_bucket_calc_bsize(xhash_this, xst_resize));
        xhash_lter = hash_bucket_find(xhash_this, xhash_elem, xhash_nkey, &xhash_find);
    }

    xhash_lter = XHASH_TABLE_CALL(emplace, xhash_this, xhash_lter, xhash_elem);
    hash_bucket_insert(xhash_this, xhash_lter, xhash_nkey);

    if (XHASH_NULL != xbt_clash)
        *xbt_clash = XHASH_FALSE;
    return (xhash_iter_t)xhash_lter;
}

/**********************************************************/
/**
 * @brief 删除 xstd_hash_t 对象中的指定（迭代器对应的）节点元素。
 * 
 * @param [in,out] xhash_this : xstd_hash_t 对象。
 * @param [in    ] xiter_pos  : 所要删除的节点（迭代器）。
 * 
 * @return xhash_iter_t : 返回 xiter_pos 的后继节点。
 */
xhash_iter_t std_hash_erase(xhash_this_t xhash_this, xhash_iter_t xiter_pos)
{
    XASSERT(XHASH_NULL != xhash_this);
    XASSERT(XHASH_NULL != xiter_pos);

    hash_bucket_erase(
        xhash_this,
        (xhash_lter_t)xiter_pos,
        XHASH_BUCKET_NKEY(
            xhash_this, XHASH_LTER_ELEM((xhash_lter_t)xiter_pos)));

    return (xhash_iter_t)
        XHASH_TABLE_CALL(erase, xhash_this, (xhash_lter_t)xiter_pos);
}

/**********************************************************/
/**
 * @brief 删除 xstd_hash_t 对象中的指定节点元素值。
 * 
 * @param [in,out] xhash_this : xstd_hash_t 对象。
 * @param [in    ] xhash_elem : 所要删除的节点（迭代器）。
 * 
 * @return xhash_size_t : 删除的节点数量（0 或 1）。
 */
xhash_size_t std_hash_erase_elem(
                xhash_this_t xhash_this,
                xhash_elem_t xhash_elem)
{
    XASSERT(XHASH_NULL != xhash_this);
    XASSERT(XHASH_NULL != xhash_elem);

    xhash_bool_t xhash_find = XHASH_FALSE;
    xhash_nkey_t xhash_nkey = XHASH_BUCKET_NKEY(xhash_this, xhash_elem);
    xhash_lter_t xhash_lter = hash_bucket_find(xhash_this, xhash_elem, xhash_nkey, &xhash_find);
    if (xhash_find)
    {
        hash_bucket_erase(xhash_this, xhash_lter, xhash_nkey);
        XHASH_TABLE_CALL(erase, xhash_this, xhash_lter);
        return 1;
    }

    return 0;
}

/**********************************************************/
/**
 * @brief 
 * 删除 xstd_hash_t 对象中的指定
 * 区间 [ xiter_first, xiter_last ) 节点元素。
 * 
 * @param [in,out] xhash_this  : xstd_hash_t 对象。
 * @param [in    ] xiter_first : 所删除区间的起始节点。
 * @param [in    ] xiter_last  : 所删除区间的结束节点。
 * 
 * @return xhash_iter_t : 返回 xiter_last 节点。
 */
xhash_iter_t std_hash_erase_range(
                xhash_this_t xhash_this,
                xhash_iter_t xiter_first,
                xhash_iter_t xiter_last)
{
    XASSERT(XHASH_NULL != xhash_this);
    XASSERT(XHASH_NULL != xiter_first);
    XASSERT(XHASH_NULL != xiter_last);

    if (xiter_first == xiter_last)
    {
        return xiter_last;
    }

    return (xhash_iter_t)hash_table_erase(
        xhash_this, (xhash_lter_t)xiter_first, (xhash_lter_t)xiter_last);
}

/**********************************************************/
/**
 * @brief 
 * 将 xhash_other 中的 节点元素 转移到 xhash_this 中。
 * @note 
 * 若 xhash_other 中的 某个节点元素，在 xhash_this 中有相同的值，
 * 则不对该节点元素进行转移操作，依然会保留在原来的 xhash_other 中。
 * 
 * @param [in,out] xhash_this  : 接收 转移节点元素 的 xstd_hash_t 对象。
 * @param [in,out] xhash_other : 被移出 节点元素 的 xstd_hash_t 对象。
 */
xhash_void_t std_hash_merge(
                xhash_this_t xhash_this,
                xhash_this_t xhash_other)
{
    XASSERT(XHASH_NULL != xhash_this);
    XASSERT(XHASH_NULL != xhash_other);
    XASSERT(XHASH_ISSAME_TYPE(xhash_this, xhash_other));

    if (xhash_this == xhash_other)
    {
        return;
    }

    xhash_lter_t xlter_trav = XHASH_LTER_BEGIN(xhash_other);
    xhash_lter_t xlter_oend = XHASH_LTER_END(xhash_other);
    xhash_lter_t xlter_node = XHASH_NULL;

    xhash_bool_t xhash_find = XHASH_FALSE;
    xhash_nkey_t xhash_nkey = XHASH_NULL;
    xhash_lter_t xhash_lter = XHASH_NULL;
    xhash_elem_t xhash_elem = XHASH_NULL;
    xhash_size_t xst_resize = 0;

    while (xlter_trav != xlter_oend)
    {
        xlter_node = xlter_trav;
        xlter_trav = XHASH_LTER_NEXT(xlter_trav);

        xhash_elem = XHASH_LTER_ELEM(xlter_node);
        xhash_nkey = XHASH_BUCKET_NKEY(xhash_this, xhash_elem);
        xhash_lter = hash_bucket_find(xhash_this, xhash_elem, xhash_nkey, &xhash_find);
        if (xhash_find)
        {
            continue;
        }

        xst_resize = XHASH_TABLE_SIZE(xhash_this) + 1;
        XASSERT(xst_resize <= XHASH_MAX_SIZE(xhash_this));
        if (hash_bucket_is_overload(xhash_this, xst_resize))
        {
            hash_bucket_rehash(xhash_this, hash_bucket_calc_bsize(xhash_this, xst_resize));
            xhash_lter = hash_bucket_find(xhash_this, xhash_elem, xhash_nkey, &xhash_find);
        }

        XHASH_LTER_REMOVE(xhash_other, xlter_node);
        XHASH_LTER_INSERT(xhash_this, xhash_lter, xlter_node);
        hash_bucket_insert(xhash_this, xlter_node, xhash_nkey);
    }
}

/**********************************************************/
/**
 * @brief 
 * 统计 xstd_hash_t 对象中，
 * 为 xhash_elem 节点元素值的数量（0 或 1）。
 * 
 * @param [in,out] xhash_this : xstd_hash_t 对象。
 * @param [in    ] xhash_elem : 所统计的节点元素值。
 * 
 * @return xhash_size_t : 统计到的数量（0 或 1）。
 */
xhash_size_t std_hash_count(
                xhash_this_t xhash_this,
                xhash_elem_t xhash_elem)
{
    XASSERT(XHASH_NULL != xhash_this);
    XASSERT(XHASH_NULL != xhash_elem);

    xhash_bool_t xhash_find = XHASH_FALSE;
    xhash_lter_t xhash_lter = hash_bucket_find(
                                xhash_this,
                                xhash_elem,
                                XHASH_BUCKET_NKEY(xhash_this, xhash_elem),
                                &xhash_find);

    return (xhash_size_t)xhash_find;
}

/**********************************************************/
/**
 * @brief 
 * 查找 xstd_hash_t 对象中，
 * 为 xhash_elem 节点元素值的迭代器位置。
 * 
 * @param [in,out] xhash_this : xstd_hash_t 对象。
 * @param [in    ] xhash_elem : 所查找的节点元素值。
 * 
 * @return xhash_iter_t : 
 * 所查找的节点元素迭代器位置，
 * 或为 std_hash_end(xhash_this) 末端迭代器。
 */
xhash_iter_t std_hash_find(
                xhash_this_t xhash_this,
                xhash_elem_t xhash_elem)
{
    XASSERT(XHASH_NULL != xhash_this);
    XASSERT(XHASH_NULL != xhash_elem);

    xhash_bool_t xhash_find = XHASH_FALSE;
    xhash_lter_t xhash_lter = hash_bucket_find(
                                xhash_this,
                                xhash_elem,
                                XHASH_BUCKET_NKEY(xhash_this, xhash_elem),
                                &xhash_find);

    return (xhash_iter_t)(xhash_find ? xhash_lter : XHASH_LTER_END(xhash_this));
}

/**********************************************************/
/**
 * @brief 返回 xstd_hash_t 对象的当前散列桶数量。
 */
xhash_size_t std_hash_bucket_count(xhash_this_t xhash_this)
{
    XASSERT(XHASH_NULL != xhash_this);
    return XHASH_BUCKET_SIZE(xhash_this);
}

/**********************************************************/
/**
 * @brief 返回 xstd_hash_t 对象的散列桶最大容纳数量。
 */
xhash_size_t std_hash_bucket_maxcount(xhash_this_t xhash_this)
{
    XASSERT(XHASH_NULL != xhash_this);
    return XHASH_BUCKET_MAX_SIZE(xhash_this);
}

/**********************************************************/
/**
 * @brief 计算 节点元素 对象在 xstd_hash_t 对象中的 散列键值。
 * 
 * @param [in ] xhash_this : xstd_hash_t 对象。
 * @param [in ] xhash_elem : 节点元素值。
 * 
 * @return xhash_nkey_t : 散列键值。
 */
xhash_nkey_t std_hash_bucket_nkey(
                xhash_this_t xhash_this,
                xhash_elem_t xhash_elem)
{
    XASSERT(XHASH_NULL != xhash_this);
    XASSERT(XHASH_NULL != xhash_elem);
    return XHASH_BUCKET_NKEY(xhash_this, xhash_elem);
}

/**********************************************************/
/**
 * @brief 返回 xstd_hash_t 对象指定 散列桶 中当前存储的节点数量。
 * 
 * @param [in ] xhash_this : xstd_hash_t 对象。
 * @param [in ] xhash_nkey : 所指定的 散列桶索引键值。
 * 
 * @return xhash_size_t : 指定 散列桶 中当前存储的节点数量。
 */
xhash_size_t std_hash_bucket_size(
                xhash_this_t xhash_this,
                xhash_nkey_t xhash_nkey)
{
    XASSERT(XHASH_NULL != xhash_this);

    xhash_size_t xhash_size = 0;
    xhash_vter_t xhash_vkey = XHASH_BUCKET_VKEY(xhash_this, xhash_nkey);
    xhash_lter_t xlter_trav = xhash_vkey->xlter_head;

    if (xlter_trav != XHASH_LTER_END(xhash_this))
    {
        for (xhash_size = 1; xlter_trav != xhash_vkey->xlter_tail; ++xhash_size)
        {
            xlter_trav = XHASH_LTER_NEXT(xlter_trav);
        }
    }

    return xhash_size;
}

/**********************************************************/
/**
 * @brief 返回 xstd_hash_t 对象指定 散列桶 所存储节点的起始迭代器。
 * 
 * @param [in ] xhash_this : xstd_hash_t 对象。
 * @param [in ] xhash_nkey : 所指定的 散列桶索引键值。
 * 
 * @return xhash_iter_t : 指定 散列桶 所存储节点的起始迭代器。
 */
xhash_iter_t std_hash_bucket_begin(
                xhash_this_t xhash_this,
                xhash_nkey_t xhash_nkey)
{
    XASSERT(XHASH_NULL != xhash_this);
    return (xhash_iter_t)XHASH_BUCKET_VKEY(xhash_this, xhash_nkey)->xlter_head;
}

/**********************************************************/
/**
 * @brief 返回 xstd_hash_t 对象指定 散列桶 所存储节点的结束迭代器。
 * 
 * @param [in ] xhash_this : xstd_hash_t 对象。
 * @param [in ] xhash_nkey : 所指定的 散列桶索引键值。
 * 
 * @return xhash_iter_t : 指定 散列桶 所存储节点的结束迭代器。
 */
xhash_iter_t std_hash_bucket_end(
                xhash_this_t xhash_this,
                xhash_nkey_t xhash_nkey)
{
    XASSERT(XHASH_NULL != xhash_this);
    xhash_lter_t xhash_lter = 
        XHASH_BUCKET_VKEY(xhash_this, xhash_nkey)->xlter_tail;
    return (xhash_iter_t)(
                (xhash_lter != XHASH_LTER_END(xhash_this)) ?
                XHASH_LTER_NEXT(xhash_lter) : xhash_lter);
}

/**********************************************************/
/**
 * @brief 返回 xstd_hash_t 对象当前的 散列桶负载率。
 * @note  散列桶负载率 = std_hash_size() / std_hash_bucket_count() 。
 */
xhash_float_t std_hash_load_factor(xhash_this_t xhash_this)
{
    XASSERT(XHASH_NULL != xhash_this);
    return ((xhash_float_t)XHASH_TABLE_SIZE(xhash_this) /
            (xhash_float_t)XHASH_BUCKET_SIZE(xhash_this));
}

/**********************************************************/
/**
 * @brief 
 * 返回 xstd_hash_t 对象的 散列桶最大负载率（max load factor），
 * 其默认值为 1.0F 。
 */
xhash_float_t std_hash_maxlf(xhash_this_t xhash_this)
{
    XASSERT(XHASH_NULL != xhash_this);
    return XHASH_BUCKET_MAXF(xhash_this);
}

/**********************************************************/
/**
 * @brief 
 * 设置 xstd_hash_t 对象的 散列桶最大负载率（max load factor）。
 * @note 
 * 所设置的 xft_maxlf 值，要求 ((xft_maxlf > 0) && (NAN != xft_maxlf))。
 */
xhash_void_t std_hash_set_maxlf(
                xhash_this_t xhash_this,
                xhash_float_t xft_maxlf)
{
    XASSERT(XHASH_NULL != xhash_this);
    XASSERT((xft_maxlf > 0) && !isnan(xft_maxlf));
    XHASH_BUCKET_MAXF(xhash_this) = xft_maxlf;
}

/**********************************************************/
/**
 * @brief 设置 xstd_hash_t 对象的 散列桶数量，并重新调整 散列容器。
 * 
 * @param [in,out] xhash_this : xstd_hash_t 对象。
 * @param [in    ] xst_count  : 所设置的散列桶数量。
 */
xhash_void_t std_hash_rehash(
                xhash_this_t xhash_this,
                xhash_size_t xst_count)
{
    XASSERT(XHASH_NULL != xhash_this);

    xhash_size_t xst_bsize = 
        hash_bucket_req_minsize(xhash_this, XHASH_TABLE_SIZE(xhash_this));
    if (xst_bsize < xst_count)
    {
        xst_bsize = xst_count;
    }

    if (xst_bsize <= XHASH_BUCKET_SIZE(xhash_this))
    {
        return;
    }

    hash_bucket_rehash(xhash_this, xst_bsize);
}

/**********************************************************/
/**
 * @brief 预定 xstd_hash_t 对象的节点元素 容量，并重新调整 散列容器。
 * 
 * @param [in,out] xhash_this : xstd_hash_t 对象。
 * @param [in    ] xst_count  : 所设置的 节点元素 容量。
 */
xhash_void_t std_hash_reserve(
                xhash_this_t xhash_this,
                xhash_size_t xst_count)
{
    XASSERT(XHASH_NULL != xhash_this);

    std_hash_rehash(
        xhash_this,
        (xhash_size_t)(
            (xhash_float_t)(xst_count) / XHASH_BUCKET_MAXF(xhash_this) + 0.5F));
}

/**********************************************************/
/**
 * @brief 返回 xstd_hash_t 对象的起始节点迭代器。
 */
xhash_iter_t std_hash_begin(xhash_this_t xhash_this)
{
    XASSERT(XHASH_NULL != xhash_this);
    return (xhash_iter_t)XHASH_LTER_BEGIN(xhash_this);
}

/**********************************************************/
/**
 * @brief 返回 迭代器 的后继节点迭代器。
 */
xhash_iter_t std_hash_next(xhash_iter_t xiter_trav)
{
    XASSERT(XHASH_NULL != xiter_trav);
    return (xhash_iter_t)XHASH_LTER_NEXT((xhash_lter_t)xiter_trav);
}

/**********************************************************/
/**
 * @brief 返回 xstd_hash_t 对象的结束节点迭代器。
 */
xhash_iter_t std_hash_end(xhash_this_t xhash_this)
{
    XASSERT(XHASH_NULL != xhash_this);
    return (xhash_iter_t)XHASH_LTER_END(xhash_this);
}

/**********************************************************/
/**
 * @brief 返回 xstd_hash_t 对象的反向起始节点迭代器。
 */
xhash_iter_t std_hash_rbegin(xhash_this_t xhash_this)
{
    XASSERT(XHASH_NULL != xhash_this);
    return (xhash_iter_t)XHASH_LTER_RBEGIN(xhash_this);
}

/**********************************************************/
/**
 * @brief 返回 反向迭代器 的后继节点迭代器。
 */
xhash_iter_t std_hash_rnext(xhash_iter_t xiter_trav)
{
    XASSERT(XHASH_NULL != xiter_trav);
    return (xhash_iter_t)XHASH_LTER_PREV((xhash_lter_t)xiter_trav);
}

/**********************************************************/
/**
 * @brief 返回 xstd_hash_t 对象的反向结束节点迭代器。
 */
xhash_iter_t std_hash_rend(xhash_this_t xhash_this)
{
    XASSERT(XHASH_NULL != xhash_this);
    return (xhash_iter_t)XHASH_LTER_REND(xhash_this);
}

/**********************************************************/
/**
 * @brief 读取节点迭代器下存储的 元素。
 */
xhash_elem_t std_hash_elem(xhash_iter_t xiter_node)
{
    XASSERT(XHASH_NULL != xiter_node);
    return XHASH_LTER_ELEM((xhash_lter_t)xiter_node);
}

////////////////////////////////////////////////////////////////////////////////

#ifdef __GNUC__
#pragma GCC diagnostic pop
#endif // __GNUC__

////////////////////////////////////////////////////////////////////////////////
